<!DOCTYPE html>
<html lang='en'><head>
  <title>Leetcode | 江小凡的博客</title>
  <meta charset='utf-8'>
  <meta name="generator" content="Hugo 0.76.5" />
  <meta name = 'viewport' content = 'width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no'>
  <meta http-equiv = 'X-UA-Compatible' content = 'IE=edge'>
<meta property = 'og:locale' content = 'en_US' />
<meta property="og:type" content="article">
<meta property = 'og:title' content = 'Leetcode' />
<meta name="description" content="买卖股票简答:
class Solution: def maxProfit(self, prices): &#34;&#34;&#34; :type prices: List[int] :rtype: int &#34;&#34;&#34; min_p, max_p = 999999, 0 for i in …">
<meta property = 'og:description' content = '买卖股票简答:
class Solution: def maxProfit(self, prices): &#34;&#34;&#34; :type prices: List[int] :rtype: int &#34;&#34;&#34; min_p, max_p = 999999, 0 for i in …'>
<meta property = 'og:url' content = 'https://jxiaof.com/post/leetcode/' />
<meta property = 'og:image' content = 'https://jxiaof.com/images/programmer.png'/>
<meta name = 'twitter:card' content = 'summary_large_image' />
<meta name = 'twitter:creator' content = ''>
<meta name = 'twitter:title' content = 'Leetcode' />
<meta property = 'twitter:description'  content = '买卖股票简答:
class Solution: def maxProfit(self, prices): &#34;&#34;&#34; :type prices: List[int] :rtype: int &#34;&#34;&#34; min_p, max_p = 999999, 0 for i in …'/>
<meta name = 'twitter:image' content = 'https://jxiaof.com/images/programmer.png' />
<link rel='apple-touch-icon' sizes='180x180' href='https://jxiaof.com/images/icons/apple-touch-icon.png'>
<link rel='icon' type='image/png' sizes='32x32' href='https://jxiaof.com/images/icons/favicon-32x32.png'>
<link rel='icon' type='image/png' sizes='16x16' href='https://jxiaof.com/images/icons/favicon-16x16.png'>
<link rel='manifest' href='https://jxiaof.com/images/icons/site.webmanifest'>

  <link rel='canonical' href='https://jxiaof.com/post/leetcode/'>
  <link rel = 'stylesheet' href = 'https://jxiaof.com/css/styles.b934c9412cc837b60543673c5f879b59569b1c7bea59b56896858a3b0a15220c8dbd91e80317b591a1857e31aa26b3bf8fbaca17c5bab12ff1231a272cd6bd6d.css' integrity = 'sha512-uTTJQSzIN7YFQ2c8X4ebWVabHHvqWbVoloWKOwoVIgyNvZHoAxe1kaGFfjGqJrO/j7rKF8W6sS/xIxonLNa9bQ=='>
</head>

  <body><div class = 'nav-drop'>
  <div class = 'nav-body'>
      <a href = 'https://jxiaof.com/about/' class = 'nav_item'>About</a>
    <div class = 'nav-close'></div>
  </div>
</div><header class = 'nav' >
  <nav class = 'nav-menu'>
    <a href='https://jxiaof.com/' class = 'nav-brand nav_item'>江小凡的博客</a>
    <div class = 'nav_bar-wrap'>
      <div class = 'nav_bar'></div>
    </div>
  </nav>
</header>


    <main>
<section class = 'post_header' style = 'background-image:url(https://jxiaof.com/images/programmer.png);'>
  <h1 class='post_title'>Leetcode</h1>
</section>
<div class = 'post'>
  <article class='post_content'><p><strong>买卖股票简答:</strong></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Solution</span>:
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">maxProfit</span>(self, prices):
        <span style="color:#e6db74">&#34;&#34;&#34;
</span><span style="color:#e6db74">        :type prices: List[int]
</span><span style="color:#e6db74">        :rtype: int
</span><span style="color:#e6db74">        &#34;&#34;&#34;</span>
        min_p, max_p <span style="color:#f92672">=</span> <span style="color:#ae81ff">999999</span>, <span style="color:#ae81ff">0</span>
        <span style="color:#66d9ef">for</span> i <span style="color:#f92672">in</span> range(len(prices)):
            min_p <span style="color:#f92672">=</span> min(min_p, prices[i])
            max_p <span style="color:#f92672">=</span> max(max_p, prices[i] <span style="color:#f92672">-</span> min_p)
        <span style="color:#66d9ef">return</span> max_p
</code></pre></div><p><strong>lru:</strong></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">
<span style="color:#75715e"># 使用有序字典(dict + 双向链表)</span>

<span style="color:#f92672">from</span> collections <span style="color:#f92672">import</span> OrderedDict

<span style="color:#66d9ef">class</span> <span style="color:#a6e22e">LRUCache</span>:

    <span style="color:#66d9ef">def</span> __init__(self, size):

        self<span style="color:#f92672">.</span>size <span style="color:#f92672">=</span> size

        self<span style="color:#f92672">.</span>linked_map <span style="color:#f92672">=</span> OrderedDict()

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">set</span>(self, key, value):

        <span style="color:#66d9ef">if</span> key <span style="color:#f92672">in</span> self<span style="color:#f92672">.</span>linked_map:

            self<span style="color:#f92672">.</span>linked_map<span style="color:#f92672">.</span>pop(key)

        <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>size <span style="color:#f92672">==</span> len(self<span style="color:#f92672">.</span>linked_map):

            self<span style="color:#f92672">.</span>linked_map<span style="color:#f92672">.</span>popitem(last<span style="color:#f92672">=</span>False)

        self<span style="color:#f92672">.</span>linked_map<span style="color:#f92672">.</span>update({key: value})

    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">get</span>(self, key):

        value <span style="color:#f92672">=</span> self<span style="color:#f92672">.</span>linked_map<span style="color:#f92672">.</span>get(key)

        self<span style="color:#f92672">.</span>linked_map<span style="color:#f92672">.</span>pop(key)

        self<span style="color:#f92672">.</span>linked_map<span style="color:#f92672">.</span>update({key: value})

        <span style="color:#66d9ef">return</span> value

</code></pre></div><p><strong>二分法</strong></p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">BinarySearch</span>(array: list, t: int) <span style="color:#f92672">-&gt;</span> int:
    <span style="color:#e6db74">&#39;&#39;&#39;
</span><span style="color:#e6db74">    index a item in object array
</span><span style="color:#e6db74">    :param array: [1, 2, 3, 34, 56, 57, 78, 90, 107]
</span><span style="color:#e6db74">    :param t: 4
</span><span style="color:#e6db74">    :return: item index
</span><span style="color:#e6db74">    &#39;&#39;&#39;</span>
    low <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>
    height <span style="color:#f92672">=</span> len(array) <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
    <span style="color:#66d9ef">while</span> low <span style="color:#f92672">&lt;</span> height:
        mid <span style="color:#f92672">=</span> (low<span style="color:#f92672">+</span>height) <span style="color:#f92672">//</span> <span style="color:#ae81ff">2</span>
        <span style="color:#66d9ef">if</span> array[mid] <span style="color:#f92672">&lt;</span> t:
            low <span style="color:#f92672">=</span> mid <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
        <span style="color:#66d9ef">elif</span> array[mid] <span style="color:#f92672">&gt;</span> t:
            height <span style="color:#f92672">=</span> mid <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
        <span style="color:#66d9ef">else</span>:
            <span style="color:#66d9ef">return</span> mid
    <span style="color:#66d9ef">return</span> height <span style="color:#66d9ef">if</span> array[low] <span style="color:#f92672">==</span> t <span style="color:#66d9ef">else</span> f<span style="color:#e6db74">&#34;Not exist in object array, this new value may be place in: {height} !&#34;</span>


<span style="color:#66d9ef">if</span> __name__ <span style="color:#f92672">==</span> <span style="color:#e6db74">&#34;__main__&#34;</span>:
    <span style="color:#66d9ef">print</span>(BinarySearch([<span style="color:#ae81ff">1</span>, <span style="color:#ae81ff">2</span>, <span style="color:#ae81ff">3</span>, <span style="color:#ae81ff">34</span>, <span style="color:#ae81ff">56</span>, <span style="color:#ae81ff">57</span>, <span style="color:#ae81ff">78</span>, <span style="color:#ae81ff">90</span>, <span style="color:#ae81ff">107</span>], <span style="color:#ae81ff">4</span>))
</code></pre></div><p><strong>最长节点</strong></p>
<p>给定一个二叉树，找出其最大深度。</p>
<p>二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。</p>
<p>说明: 叶子节点是指没有子节点的节点。</p>
<p>示例：
给定二叉树 [3,9,20,null,null,15,7]，</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">    <span style="color:#ae81ff">3</span>
   <span style="color:#f92672">/</span> \
  <span style="color:#ae81ff">9</span>  <span style="color:#ae81ff">20</span>
    <span style="color:#f92672">/</span>  \
   <span style="color:#ae81ff">15</span>   <span style="color:#ae81ff">7</span>
</code></pre></div><p>返回它的最大深度 3 。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Solution</span>:
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">maxDepth</span>(self, root: TreeNode) <span style="color:#f92672">-&gt;</span> int:
        <span style="color:#66d9ef">if</span> root <span style="color:#f92672">==</span> None:
            <span style="color:#66d9ef">return</span> <span style="color:#ae81ff">0</span>
        <span style="color:#66d9ef">elif</span> root<span style="color:#f92672">.</span>right <span style="color:#f92672">==</span> None <span style="color:#f92672">and</span> root<span style="color:#f92672">.</span>left <span style="color:#f92672">==</span> None :
            <span style="color:#66d9ef">return</span> <span style="color:#ae81ff">1</span>
        <span style="color:#66d9ef">else</span>:
            <span style="color:#66d9ef">return</span> <span style="color:#ae81ff">1</span> <span style="color:#f92672">+</span> max(self<span style="color:#f92672">.</span>maxDepth(root<span style="color:#f92672">.</span>left) , self<span style="color:#f92672">.</span>maxDepth(root<span style="color:#f92672">.</span>right))
</code></pre></div><p><strong>Employee 表</strong></p>
<p>Employee 表包含所有员工，他们的经理也属于员工。每个员工都有一个 Id，此外还有一列对应员工的经理的 Id。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#f92672">+----+-------+--------+-----------+</span>
<span style="color:#f92672">|</span> Id <span style="color:#f92672">|</span> Name  <span style="color:#f92672">|</span> Salary <span style="color:#f92672">|</span> ManagerId <span style="color:#f92672">|</span>
<span style="color:#f92672">+----+-------+--------+-----------+</span>
<span style="color:#f92672">|</span> <span style="color:#ae81ff">1</span>  <span style="color:#f92672">|</span> Joe   <span style="color:#f92672">|</span> <span style="color:#ae81ff">70000</span>  <span style="color:#f92672">|</span> <span style="color:#ae81ff">3</span>         <span style="color:#f92672">|</span>
<span style="color:#f92672">|</span> <span style="color:#ae81ff">2</span>  <span style="color:#f92672">|</span> Henry <span style="color:#f92672">|</span> <span style="color:#ae81ff">80000</span>  <span style="color:#f92672">|</span> <span style="color:#ae81ff">4</span>         <span style="color:#f92672">|</span>
<span style="color:#f92672">|</span> <span style="color:#ae81ff">3</span>  <span style="color:#f92672">|</span> Sam   <span style="color:#f92672">|</span> <span style="color:#ae81ff">60000</span>  <span style="color:#f92672">|</span> NULL      <span style="color:#f92672">|</span>
<span style="color:#f92672">|</span> <span style="color:#ae81ff">4</span>  <span style="color:#f92672">|</span> Max   <span style="color:#f92672">|</span> <span style="color:#ae81ff">90000</span>  <span style="color:#f92672">|</span> NULL      <span style="color:#f92672">|</span>
<span style="color:#f92672">+----+-------+--------+-----------+</span>
</code></pre></div><p>给定 Employee 表，编写一个 SQL 查询，该查询可以获取收入超过他们经理的员工的姓名。在上面的表格中，Joe 是唯一一个收入超过他的经理的员工。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#f92672">+----------+</span>
<span style="color:#f92672">|</span> Employee <span style="color:#f92672">|</span>
<span style="color:#f92672">+----------+</span>
<span style="color:#f92672">|</span> Joe      <span style="color:#f92672">|</span>
<span style="color:#f92672">+----------+</span>
</code></pre></div><div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-sql" data-lang="sql"><span style="color:#66d9ef">SELECT</span>
	b.NAME <span style="color:#66d9ef">AS</span> Employee 
<span style="color:#66d9ef">FROM</span>
	Employee <span style="color:#66d9ef">AS</span> a
	<span style="color:#66d9ef">INNER</span> <span style="color:#66d9ef">JOIN</span> Employee <span style="color:#66d9ef">AS</span> b <span style="color:#66d9ef">ON</span> a.id <span style="color:#f92672">=</span> b.ManagerId 
<span style="color:#66d9ef">WHERE</span>
	b.Salary <span style="color:#f92672">&gt;</span> a.Salary
</code></pre></div>
    <div class = 'post_extra'><div class = 'copy' data-share = 'Share Story' data-copied = 'Link Copied'>
  <svg>
    <use xlink:href="#copy"></use>
  </svg>  
</div>

    </div>

  </article>
  <div class="post-comment">
       
       <h3>Comments welcome !</h3>



<div id="vcomments"></div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
 <script type="text/javascript">
   new Valine({
       el: '#vcomments' ,
       appId: 'xb5Xl8O60fXEK4d13KsazkkL-gzGzoHsz',
       appKey: 'qyztiJ2tgf6AhvsrH088N29o',
       notify: 'false', 
       verify: 'false', 
       avatar:'mm', 
       placeholder: '说说你的看法吧...',
       visitor: 'true'
   });
 </script>
  </div>
  <aside><h3></h3>
<ul class='posts aside'>
<li class = 'post_item'>
  <a class = 'post_card' href='https://jxiaof.com/post/first/' title = 'ABOUT MYSELF' style = 'background-image: url(https://jxiaof.com/images/speakers.jpg);'>
  </a>
  <div class = 'excerpt'>
    <div class = 'excerpt_meta'><div class = 'copy' data-share = 'Share Story' data-copied = 'Link Copied'>
  <svg>
    <use xlink:href="#copy"></use>
  </svg>  
</div>

    </div>
    <h3 class = 'post_link'>
      <a href='https://jxiaof.com/post/first/'>ABOUT MYSELF</a>
    </h3>
    <p class = 'pale'><p>​        I am a light game enthusiast with poor gastrointestinal function. I go to bed …</p></p>
  </div>
</li>

<li class = 'post_item'>
  <a class = 'post_card' href='https://jxiaof.com/post/%E8%B0%88%E8%B0%88%E5%AE%9E%E9%99%85%E4%BD%BF%E7%94%A8sql%E5%BC%80%E5%8F%91/' title = 'sql使用手记' style = 'background-image: url(https://jxiaof.com/images/database.png);'>
  </a>
  <div class = 'excerpt'>
    <div class = 'excerpt_meta'><div class = 'copy' data-share = 'Share Story' data-copied = 'Link Copied'>
  <svg>
    <use xlink:href="#copy"></use>
  </svg>  
</div>

    </div>
    <h3 class = 'post_link'>
      <a href='https://jxiaof.com/post/%E8%B0%88%E8%B0%88%E5%AE%9E%E9%99%85%E4%BD%BF%E7%94%A8sql%E5%BC%80%E5%8F%91/'>sql使用手记</a>
    </h3>
    <p class = 'pale'><p>[toc]</p>
<p>​    Sql同样是一门编程语言，在某种意义上来讲，大部分的程序员写的代码都可以通过sql实现，sql应当是后端程序员基本功。sql在排查数据，如同脚本一样简单直接高 …</p></p>
  </div>
</li>

</ul>

  </aside>
</div>
<script src = 'https://jxiaof.com/js/autosize.min.js'></script>
<script src = 'https://jxiaof.com/js/timeago.js'></script>
    </main><svg width="0" height="0" class="hidden">
  <symbol viewBox="0 0 699.428 699.428" xmlns="http://www.w3.org/2000/svg" id="copy">
    <path d="M502.714 0H240.428C194.178 0 153 42.425 153 87.429l-25.267.59c-46.228 0-84.019 41.834-84.019 86.838V612c0 45.004 41.179 87.428 87.429 87.428H459c46.249 0 87.428-42.424 87.428-87.428h21.857c46.25 0 87.429-42.424 87.429-87.428v-349.19zM459 655.715H131.143c-22.95 0-43.714-21.441-43.714-43.715V174.857c0-22.272 18.688-42.993 41.638-42.993l23.933-.721v393.429C153 569.576 194.178 612 240.428 612h262.286c0 22.273-20.765 43.715-43.714 43.715zm153-131.143c0 22.271-20.765 43.713-43.715 43.713H240.428c-22.95 0-43.714-21.441-43.714-43.713V87.429c0-22.272 20.764-43.714 43.714-43.714H459c-.351 50.337 0 87.975 0 87.975 0 45.419 40.872 86.882 87.428 86.882H612zm-65.572-349.715c-23.277 0-43.714-42.293-43.714-64.981V44.348L612 174.857zm-43.714 131.537H306c-12.065 0-21.857 9.77-21.857 21.835s9.792 21.835 21.857 21.835h196.714c12.065 0 21.857-9.771 21.857-21.835 0-12.065-9.792-21.835-21.857-21.835zm0 109.176H306c-12.065 0-21.857 9.77-21.857 21.834 0 12.066 9.792 21.836 21.857 21.836h196.714c12.065 0 21.857-9.77 21.857-21.836 0-12.064-9.792-21.834-21.857-21.834z"
    ></path>
  </symbol>
  <symbol viewBox="0 0 60.015 60.015" xmlns="http://www.w3.org/2000/svg" id="reply">
    <path d="M42.007 0h-24c-9.925 0-18 8.075-18 18v14c0 9.59 7.538 17.452 17 17.973v8.344a1.694 1.694 0 0 0 1.699 1.698c.44 0 .873-.173 1.198-.498l1.876-1.876C26.708 52.713 33.259 50 40.227 50h1.78c9.925 0 18-8.075 18-18V18c0-9.925-8.075-18-18-18zm16 32c0 8.822-7.178 16-16 16h-1.78c-7.502 0-14.556 2.921-19.86 8.226l-1.359 1.359V44a1 1 0 1 0-2 0v3.949c-8.356-.52-15-7.465-15-15.949V18c0-8.822 7.178-16 16-16h24c8.822 0 16 7.178 16 16v14z"></path>
  </symbol>
</svg>
<footer class = 'footer'>
  <div class = 'footer_inner wrap pale'>
    <p>&copy;&nbsp;<span class = 'year'></span>&nbsp;江小凡的博客.
    Designed by  <a href = 'https://www.github.com/jxiaof' title = 'Linkedin Profile'>江小凡</a></p>
  </div>
</footer>
<script src = 'https://jxiaof.com/js/index.min.c3b0a769e56310d4359f30762ab615db8cd6ce33d555ee7f68d25e8a40c63ce18bf6b273d35a9b5c033a7f6e71b1d424e74d9f542d93482215c671b3f31f885f.js'></script>

  </body>
</html>
